package org.ala.linshen.dp;

/**
 *
 * 给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。
 *
 * 请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。
 *
 * abs(x) 定义如下：
 *
 * 如果 x 是负整数，那么 abs(x) = -x 。
 * 如果 x 是非负整数，那么 abs(x) = x 。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,-3,2,3,-4]
 * 输出：5
 * 解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。
 * 示例 2：
 *
 * 输入：nums = [2,-5,1,-4,3,-2]
 * 输出：8
 * 解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 * @author ala
 * @date 2024-09-15 17:32
 */
public class Q1749 {
    public static void main(String[] args) {
        Q1749 q = new Q1749();

//        int[] nums = {1,-3,2,3,-4};
//        int[] nums = {2,-5,1,-4,3,-2};
        int[] nums = {-1};

        System.out.println(q.maxAbsoluteSum(nums));
    }
    public int maxAbsoluteSum(int[] nums) {
        return V1(nums);
    }
    /**
     * 最大最小分别dp一遍，两者绝对值取大
     */
    protected int V1(int[] nums) {
        //  最大子数组和 和 最小子数组和
        int mxp = Math.max(nums[0], 0), mx = mxp,
            mnp = Math.min(nums[0], 0), mn = mnp;

        for (int i = 1 ; i < nums.length ; i++) {
            //  取最大
            int v = Math.max(mxp + nums[i], nums[i]);
            v = Math.max(v, 0);
            mx = Math.max(mx, v);
            mxp = v;
            //  取最小
            v = Math.min(mnp + nums[i], nums[i]);
            v = Math.min(v, 0);
            mn = Math.min(mn, v);
            mnp = v;
        }

        return Math.max(mx, -mn);
    }

}
